package com.masterlu.leetcode.daily.linkedlist.medium;

import com.masterlu.leetcode.daily.linkedlist.ListNode;

/**
 * 反转链表指定区域元素
 * https://leetcode-cn.com/problems/reverse-linked-list-ii/
 *
 * @Author：masterlu
 * @Date：2021/4/12 10:38 上午
 */
public class M92ReverseBetween {

    public ListNode reverseBetween(ListNode head, int left, int right) {

        //将head需要反转的部分断开，反转完成后，进行重新连接
        if (null == head || null == head.next) {
            return head;
        }
        ListNode leftHead = head;
        ListNode reverHead = null;
        ListNode rightHead = null;
        ListNode curr = head;
        int size = 1;
        while (size != right + 1) {
            if (size == left) {
                reverHead = curr.next;
                curr.next = null;
                curr = reverHead;
            }
            if (size == right) {
                rightHead = curr.next;
                curr.next = null;
            }
            curr = curr.next;
        }

        return head;
    }

    /**
     * 官方答案
     * @return
     */
    public ListNode reverseBetween2(ListNode head,int left,int right){
        //因头节点可能发生发生变化，使用虚拟头节点
        ListNode dummyNode = new ListNode(-1, head);

        ListNode pre = dummyNode;

        //第一，从虚节点走left-1步，到达left节点前一个节点
        for (int i =0; i< left-1;i++){
            pre = pre.next;
        }

        //第二，再走right-left-1步，达到right节点
        ListNode rightNode = pre;
        for (int i = 0;i < right-left-1;i++){
            rightNode = rightNode.next;
        }
        //第三，切出子链
        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;
        pre.next = null;
        rightNode.next = null;
        //第四，反正链表
        reverseLinkedList(leftNode);

        //第五，拼接炼表
        pre.next = rightNode;
        leftNode.next = curr;

        return dummyNode;
    }

    private void reverseLinkedList(ListNode leftNode) {
        ListNode pre = null;
        ListNode curr = leftNode;
        while (curr != null){
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
    }

}
